<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <title>Title</title>
</head>
<body>
<script>
  // 背包问题
  function knapsack (weights, values, weight) {
    const n = weights.length
    const f = new Array(n)
    f[-1] = new Array(weight + 1).fill(0)
    // console.log(f)

    for (let i = 0; i < n; i ++) {
      f[i] = new Array(weight + 1).fill(0)

      for (let j = 0; j <= weight; j ++) {
        if (j < weights[i]) {
          f[i][j] = f[i - 1][j]
        } else {
          f[i][j] = Math.max(f[i - 1][j - weights[i]] + values[i], f[i - 1][j])
        }
      }
    }

    return f[n - 1][weight]
  }

  const weights = [2, 2, 6, 5, 4]
  const values = [6, 3, 5, 4, 6]
  console.log(knapsack(weights, values, 10))


  // 如果用递归形式模拟背包问题，前提是每个物品数量无限
  // function knapsack (weight) {
  //   if (weight < weights[0]) {
  //     return 0
  //   }
  //
  //   let maxValue = 0
  //
  //   for (let i = 0; i < weights.length; i ++) {
  //     const leftWeight = weight - weights[i]
  //     let leftValue
  //     if (leftWeight >= 0) {
  //       leftValue = knapsack(leftWeight)
  //     }
  //
  //     if (leftWeight >= 0 && (maxValue === 0 || (leftValue + values[i]) > maxValue)) {
  //       maxValue = values[i] + leftValue
  //     }
  //
  //   }
  //
  //   return maxValue
  // }
  //
  // console.log(knapsack(4))

  // 找零问题（表格模拟）
  function makeChange (changeTypes, amount) {
    const n = changeTypes.length
    const f = new Array(n)
    f[-1] = new Array(amount + 1).fill([])

    for (let i = 0; i < n; i ++) {
      f[i] = new Array(amount + 1).fill([])

      for (let j = 0; j <= amount; j ++) {
        if (j < changeTypes[i]) {
          f[i][j] = f[i - 1][j]
        } else {
          let min = []
          let count = Math.floor(j / changeTypes[i])
          while (count > 0) {
            min = min.concat(changeTypes[i])
            count --
          }

          const top = f[i - 1][j]
          const remainder = j % changeTypes[i]
          if (f[i - 1][remainder].length + min.length < top.length) {
            f[i][j] = f[i - 1][remainder].concat(min)
          } else {
            f[i][j] = top.concat(min)
          }

        }
      }
    }

    return f[n - 1][amount]
  }

  const changeTypes = [1, 5, 10, 20, 50, 100]
  console.log(makeChange(changeTypes, 22))


  // 找零问题（递归）
  const cache = {}
  function makeChange2 (amount) {
    if (amount === 0) return []

    if (cache[amount]) return cache[amount]

    let min = []

    for (let i = 0; i < changeTypes.length; i ++) {
      const leftAmount = amount - changeTypes[i]
      let leftMin
      if (leftAmount >= 0) {
        leftMin = makeChange2(leftAmount)
      }

      if (leftAmount >=0 && (!min.length || leftMin.length + 1 < min.length)) {
        min = leftMin.concat(changeTypes[i])
      }
    }

    return cache[amount] = min
  }

  console.log(makeChange2(22))


  // 求最长公共子序列的长度
  function LCS (str1, str2) {
    const len1 = str1.length
    const len2 = str2.length

    const f = []
    f[-1] = Array(len2).fill(0)
    f[-1][-1] = 0

    for (let i = 0; i < len1; i ++) {
      f[i] = Array(len2).fill(0)
      f[i][-1] = 0
      for (let j = 0; j < len2; j ++) {
        if (str1.charAt(i) === str2.charAt(j)) {
          f[i][j] = f[i - 1][j - 1] + 1
        } else {
          f[i][j] = Math.max(f[i - 1][j], f[i][j - 1])
        }
      }
    }
    console.log(f)
    return f[len1 - 1][len2 - 1]
  }
  console.log(LCS('acbaed', 'abcadf'))

  // 求最长公共子序列的长度和最长子序列
  class Ele {
    constructor(len = 0, subs = []) {
      this.len = len
      this.subs = subs
    }
  }

  function LCS2 (str1, str2) {
    const len1 = str1.length
    const len2 = str2.length

    const f = []
    f[-1] = Array(len2).fill(new Ele())
    f[-1][-1] = new Ele()

    for (let i = 0; i < len1; i ++) {
      f[i] = Array(len2).fill(new Ele())
      f[i][-1] = new Ele()
      for (let j = 0; j < len2; j ++) {
        if (str1.charAt(i) === str2.charAt(j)) {
          const ele = f[i - 1][j - 1]
          f[i][j] = new Ele(ele.len + 1, ele.subs.length ? ele.subs.map(sub => `${sub}${str1.charAt(i)}`) : [str1.charAt(i)])
        } else {
          const left = f[i - 1][j]
          const top = f[i][j - 1]
          if (left.len === top.len) {
            f[i][j] = new Ele(left.len, [...new Set(left.subs.concat(top.subs))])
          } else if (left.len > top.len) {
            f[i][j] = left
          } else {
            f[i][j] = top
          }
        }
      }
    }
    console.log(f)
    return f[len1 - 1][len2 - 1]
  }
  console.log(LCS2('acbaed', 'abcadf'))
</script>
</body>
</html>
